package Leetcode.动态规划;

/**
 * @Author: kirito
 * @Date: 2024/3/26 14:10
 * @Description:
 * 最长递增子序列
 * 中等
 * 相关标签
 * 相关企业
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 *
 * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
 * 子序列
 * 。
 *
 *
 * 示例 1：
 *
 * 输入：nums = [10,9,2,5,3,7,101,18]
 * 输出：4
 * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
 * 示例 2：
 *
 * 输入：nums = [0,1,0,3,2,3]
 * 输出：4
 * 示例 3：
 *
 * 输入：nums = [7,7,7,7,7,7,7]
 * 输出：1
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 2500
 * -104 <= nums[i] <= 104
 *https://leetcode.cn/problems/longest-increasing-subsequence/solutions/147667/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti
 */

public class lengthOfLIS {
    //动态规划
    public int lengthOfLIS(int[] nums) {
        // 如果数组为空或长度为0，则最长递增子序列的长度为0
        if (nums.length == 0) {
            return 0;
        }

        // 创建一个数组dp，用于存储到当前位置为止的最长递增子序列的长度
        int[] dp = new int[nums.length];

        // 初始化dp数组，第一个元素的最长递增子序列长度为1
        dp[0] = 1;

        // maxans用于记录全局最长递增子序列的长度，初始为1
        int maxans = 1;

        // 从第二个数开始遍历数组
        for (int i = 1; i < nums.length; i++) {
            // 初始化当前位置的最长递增子序列长度为1
            dp[i] = 1;

            // 遍历当前元素之前的所有元素
            for (int j = 0; j < i; j++) {
                // 如果当前元素大于之前的某个元素，则尝试更新dp[i]
                /*
                已知j<i，dp[j]代表当前位置为止的最长递增子序列的长度
                因为nums[i] > nums[j]
                所以dp[i] = Math.max(dp[i], dp[j] + 1);
                数学逻辑还是得证明题来写证明逻辑好理解QAQ
                 */
                if (nums[i] > nums[j]) {
                    // 更新dp[i]为dp[j] + 1和dp[i]中的较大值
                    // 这是因为如果nums[i]可以接在nums[j]后面，那么以nums[i]结尾的LIS长度至少是dp[j] + 1
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            // 更新全局最长递增子序列长度
            maxans = Math.max(maxans, dp[i]);
        }

        // 返回最长递增子序列的长度
        return maxans;
    }

    /**
     * 考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，
     * 因此我们希望每次在上升子序列最后加上的那个数尽可能的小。
     *
     *todo：emmmm不太理解这个思路怎么来的。为什么可以这么思考
     */
    public int lengthOfLIS2(int[] nums) {
        int len = 1, n = nums.length;
        if (n == 0) {
            return 0;
        }

        // 创建一个数组d，用于存储递增子序列，d[i]表示长度为i的递增子序列的最小结尾元素
        int[] d = new int[n + 1];

        // 初始化d数组，d[1]为序列的第一个元素
        d[len] = nums[0];

        // 遍历数组中的每个元素
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) {
                // 如果当前元素比d[len]大，说明找到了一个更长的递增子序列
                // 将当前元素添加到d数组的末尾，并更新len
                d[++len] = nums[i];
            } else {
                // 如果当前元素不大于d[len]，则在其左侧寻找合适的位置
                int l = 1, r = len, pos = 0; // pos用于记录待插入位置，初始为0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        // 如果d[mid]小于nums[i]，则更新pos并继续在右侧查找
                        pos = mid;
                        l = mid + 1;
                    } else {
                        // 如果d[mid]大于等于nums[i]，则继续在左侧查找
                        r = mid - 1;
                    }
                }
                // 将nums[i]放在找到的位置上，替换掉原位置上更大的数
                // 这样可以保证d数组中的每个元素都是最小的，且可以构成递增序列
                d[pos + 1] = nums[i];
            }
        }

        // 返回最长递增子序列的长度
        return len;
    }


}
